#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7,M = 50;
int t,f[M+10][20],fac[M+10],inv[M+10],ans,v[20];
string n;
inline int ksm(int x,int p)
{
	if(p == 0) return 0;
	int ans = 1;
	while(p)
	{
		if((p&1)) ans = (ans*x)%mod;
		x = (x*x)%mod;
		p >>= 1;
	}
	return ans;
}
inline int C(int x,int y)
{
	if(x == 0) return 0; 
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%lld",&t);
	fac[0] = 1;
	for(int i = 1;i <= M;i++) fac[i] = fac[i-1]*i%mod;
	for(int i = 0;i <= M;i++) inv[i] = ksm(fac[0],mod-2);
	for(int i = 1;i <= M;i++) 
		for(int j = 1;j <= 9;j++)
		{
			f[i][j] = 1;
			for(int z = i/2+1;z < i;z++)
				f[i][j] = (f[i][j]+(C(i-1,z-1)*ksm(9,i-z)%mod+C(i-1,z-1)*ksm(8,i-z)%mod)%mod)%mod;
			if(i % 2 == 0) f[i][j] = (f[i][j]+(C(i-1,i/2-1)*ksm(9,i-i/2)%mod+C(i-1,i/2-1)*ksm(8,i-i/2)%mod)%mod-(9-j)*C(i,i/2)%mod+mod)%mod;
			f[i][j] = f[i][j]*j%mod;
			//cout<<i<<" $ "<<j<<" "<<f[i][j]<<endl;
		}
	while(t--)
	{
		cin >> n;
		ans = 0;
		for(int j = 9;j >= 1;j--) v[j] = 0;
		for(int i = 1;i < n.size();i++) 
			for(int j = 1;j <= 9;j++) ans = (ans+f[i][j])%mod;
		for(int i = 0;i < n.size();i++) 
		{	
			for(int j = 1;j < n[i]-'0';j++)
			{
				if(i == 0)
				{
					if(n.size()-i+v[j] == n.size()) ans = (ans+j)%mod;
					for(int z = 0;z < n.size()-i;z++)
					{
						if(v[j]+z > (n.size()+1)/2 || (v[j]+z == (n.size()+1)/2 && n.size()%2 != 0))
							ans = (ans+(C((n.size()-i)-1,v[j]+z-1)*ksm(9,(n.size()-i)-(v[j]+z))%mod+C((n.size()-i)-1,v[j]+z-1)*ksm(8,(n.size()-i)-(v[j]+z))%mod)*j%mod)%mod;
						else if(v[j]+z == n.size()/2 && n.size() % 2 == 0) 
							ans = (ans+(C((n.size()-i)-1,v[j]+z-1)*ksm(9,(n.size()-i)-(v[j]+z))%mod+C((n.size()-i)-1,v[j]+z-1)*ksm(8,(n.size()-i)-(v[j]+z))%mod-(9-j)*C(v[j]+z,(v[j]+z)/2)%mod+mod)*j%mod)%mod;
					}
					continue;
				}
				for(int z = 0;z <= n.size()-i;z++)
				{
					if(n.size()-i+v[j] == n.size()) ans = (ans+j)%mod;
					for(int z = 0;z < n.size()-i;z++)
						if(v[j]+z > (n.size()+1)/2 || (v[j]+z == (n.size()+1)/2 && n.size()%2 != 0))
							ans = (ans+(C((n.size()-i),v[j]+z)*ksm(9,(n.size()-i)-(v[j]+z))%mod)*j%mod)%mod;
						else if(v[j]+z == n.size()/2 && n.size() % 2 == 0) 
							ans = (ans+(C((n.size()-i),v[j]+z)*ksm(9,(n.size()-i)-(v[j]+z))%mod-(9-j)*C(v[j]+z,(v[j]+z)/2)%mod+mod)*j%mod)%mod;
				}
			}
			v[n[i]-'0']++;
		}
		for(int j = 9;j >= 1;j--)
			if(v[j] >= (n.size()+1)/2)
			{
				ans = (ans+j)%mod;
				break;
			}
		printf("%lld\n",ans);
	}
	return 0;
}


